//二分查找(朴素二分查找模板)
class Solution {
public:
    int search(vector<int>& nums, int target) {
       int left = 0 , right = nums.size()-1;
       while(left <= right)
       {
           int mid = (left + right) / 2;
           if(nums[mid] < target) left = mid+1;
           else if(nums[mid] > target) right = mid-1;
           else 
               return mid;
       }
       return -1;
    }
};

//在排序数组中查找元素的第一个和最后一个位置（二分查找区间端点模板）
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
    int left = 0 , right = nums.size()-1;
    vector<int> ret(2,-1);
    //特殊情况
    if(nums.size() == 0) return ret;
    //查找区间左端点
    while(left < right)
    {
        int mid = left + (right - left)/2;
        if(nums[mid] < target) left = mid+1;
        else //>=
           right = mid;
    }
    if(nums[left] == target) ret[0] = left;
    
    //查找区间右端点
    left = 0 , right = nums.size()-1;
    while(left < right)
    {
        //[<=target][>target]
        int mid = left + (right - left +1)/2;
        if(nums[mid] > target) right = mid-1;
        else left = mid;
    }
    if(nums[left] == target) ret[1] = left;
    return ret;
    }
};

//x的平方根
class Solution {
public:
    int mySqrt(int x) {
        if(x < 1) return 0;
        int left = 1 , right = x;
        //查找左端点
        //[<=target]mid[>target]
        while(left < right)
        {
            long long mid = left + (right-left+1)/2;
            if(mid * mid <= x) left = mid;
            else right = mid-1;
        }
        return left;
    }
};

//搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0 , right = nums.size()-1;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] < target) ++left;
        return left;
    }
};

//山脉数组的峰顶索引
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1 , right = arr.size() - 2;
        //[>=target][<target]
        while(left < right)
        {
            int mid = left + (right - left + 1)/2;
            if(arr[mid] < arr[mid-1]) right = mid-1;
            else left = mid;
        }
        return left;
    }
};

//寻找峰值
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0 , right = nums.size()-1;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

